RootishArrayStack: A Space-Efficient Array Stack

Discover the need of RootishArrayStack.

The data structures that store their data in one or two arrays and avoid resizing these arrays too often, the arrays frequently are not very full. For example, immediately after a resize() operation on an ArrayStack, the backing array is only half full. Even worse, there are times when only one-third of it contains data.

Visual demonstration#

A sequence of add(i, x) and remove(i) operations on a RootishArrayStack is illustrated below. Arrows denote elements being copied.

Created with Fabric.js 3.6.6
A RootishArrayStack

1 of 5

Created with Fabric.js 3.6.6
An add operation

2 of 5

Created with Fabric.js 3.6.6
A remove operation

3 of 5

Created with Fabric.js 3.6.6
A remove operation

4 of 5

Created with Fabric.js 3.6.6
A remove operation

5 of 5

In this lesson, we discuss the RootishArrayStack data structure, that addresses the problem of wasted space. The RootishArrayStack stores nn elements using O(n)O(\sqrt n) arrays. In these arrays, at most O(n)O(\sqrt n) array locations are unused at any time. All remaining array locations are used to store data. Therefore, these data structures waste at most O(n)O(\sqrt n) space when storing nn elements.

A RootishArrayStack stores its elements in a list of rr arrays called blocks that are numbered 0,1,...,r10,1,...,r−1. See the above slides. Block bb contains b+1b + 1 elements. Therefore, all rr blocks contain a total of

1+2+3++r=r(r+1)/21 + 2 + 3 + \cdots + r = r(r + 1)/2

elements. The above formula can be obtained as shown in the following illustration:

Visual representation of the above formula
Visual representation of the above formula

In the illustration above, the number of shaded squares is the same. Together the white and shaded squares make a rectangle consisting of r(r+1)r(r + 1) squares.

Basic variables

As we might expect, the elements of the list are laid out in order within the blocks. The list element with index 00 is stored in block 00, elements with list indices 11 and 22 are stored in block 11, elements with list indices 33, 44, and 55 are stored in block 22, and so on. The main problem we have to address is that of determining, given an index ii, which block contains ii as well as the index corresponding to ii within that block.

Determining the index of ii within its block turns out to be easy. If index ii is in block bb, then the number of elements in blocks 0,,b10,\cdots,b−1 is b(b+1)/2b(b + 1)/ 2. Therefore, ii is stored at location

j=ib(b+1)/2j = i − b(b + 1)/2

within block bb. Somewhat more challenging is the problem of determining the value of bb. The number of elements that have indices less than or equal to ii is i+1i + 1. On the other hand, the number of elements in blocks 0,,b0,\cdots,b is (b+1)(b+2)/2(b + 1)(b + 2)/2. Therefore, bb is the smallest integer such that

(b+1)(b+2)/2i+1(b+1)(b+2)/2 \ge i + 1

We can rewrite this equation as

b2+3b2i0b^2 + 3b − 2i \ge 0

The corresponding quadratic equation b2+3b2i=0b^2 + 3b − 2i = 0 has two solutions: b=(3+9+8i)/2b = (−3 + \sqrt{9 + 8i})/2 and b=(39+8i)/2b = (−3 − \sqrt{9 + 8i})/2. The second solution makes no sense in our application since it always gives a negative value. Therefore, we obtain the solution b=(3+9+8i)/2b = (−3 + \sqrt{9 + 8i})/2. In general, this solution is not an integer, but going back to our inequality, we want the smallest integer bb such that b(3+9+8i)/2b \ge (−3 + \sqrt{9 + 8i})/2. This is simply

b=(3+9+8i)/2b = \lceil (-3 + \sqrt{9+8i})/2 \rceil

The i2b() method

The RootishArrayStack operations#

With this out of the way, the get(i) and set(i, x) methods are straightforward. We first compute the appropriate block bb and the appropriate index jj within the block and then perform the appropriate operation:

The get() and set() method

If we use any of the array-based data structures for representing the blocks list, then get(i) and set(i, x) will each run in constant time.

The add(i, x) method will, by now, look familiar. We first check to see if our data structure is full, by checking if the number of blocks, rr, is such that r(r+1)/2=nr(r + 1)/2 = n. If so, we call grow() to add another block. With this done, we shift elements with indices i,,n1i,\cdots, n−1 to the right by one position to make room for the new element with index ii:

The grow() method does what we expect. It adds a new block:

The grow() method

Ignoring the cost of the grow() operation, the cost of an add(i, x) operation is dominated by the cost of shifting and is therefore O(1+ni)O(1 + n − i), just like an ArrayStack.

The remove(i) operation is similar to add(i, x). It shifts the elements with indices i+1,,ni + 1,\cdots, n left by one position and then, if there is more than one empty block, it calls the shrink() method to remove all but one of the unused blocks:

The remove() method

The implementation of the shrink() method is:

The shrink() method

Once again, ignoring the cost of the shrink() operation, the cost of a remove(i) operation is dominated by the cost of shifting and is therefore O(ni).O(n − i).

main.py
arraystack.py
base.py
utils.py
Implementation of RootishArrayStack

Explanation

Let’s start our explanation from the start of main() in main.py file.

  • Line 67: It creates a new instance of the RootishArrayStack class with the type of the elements to be stored in the stack being Integer. The new instance is assigned to the variable stack.
  • Lines 69–71: It adds the elements 1, 2, and 3 to the stack at indices 0, 1, and 2, respectively.
  • Line 72: It prints the elements of stack.
  • Line 74: It removes an element from stack from index 1 using the remove() method.
  • Lines 77–78: It adds the elements 2 and 4 to stack at indices 1 and 3, respectively.
  • Line 81: It clears all the elements from stack.

DualArrayDeque: Building a Deque from Two Stacks

Analysis of RootishArrayStack